최단 경로(shortest path)
δ(u,v)={min{w(p):u→v}∞
- 다익스트라 알고리즘(그리디 알고리즘)
- 플로이드 알고리즘(동적 프로그래밍 알고리즘)
0≤i≤j≤k에 대해서
p가 v0에서 vk까지의 최단 경로일 경우,
p의 부분 경로 pij는 vi에서 vj까지의 최단 경로이다.
다익스트라, 플로이드 알고리즘은 음의 가중치를 허용하지 않는다.
벨만 포드 알고리즘 등 다른 알고리즘은 음의 가중치를 허용하기도 한다.
음의 가중치가 포함되어 있어도 순환 구조가 없으면, 동일하게 적용된다.
너비 우선 탐색을 이용하면, 순환 구조를 제외하고 그래프를 얻을 수 있다.
== 최단 경로 표현
완화(Relaxation)
지금까지 발견된 최단 경로를 개선할 수 있는 경우 검사 및 개선
remade adjList to cover edge's weights;;
#include <iostream>
#include <climits>
#define NIL -1
struct Node{
int to, weight;
Node* next=nullptr;
Node(int _to, int _weight): to(_to), weight(_weight) {}
};
struct Vertex{
int d=INT_MAX, pi=NIL;
Vertex(){}
};
struct adjList{
int nV, nE;
Node** list;
Vertex* vertex;
adjList(int _nV, int _nE): nV(_nV), nE(_nE){
this->list=new Node*[this->nV];
this->vertex=new Vertex[this->nV];
}
~adjList(){
for(int i=0; i<this->nV; ++i) delete list[i];
delete[] list;
delete[] vertex;
}
void Insert(int u, int v, int weight){
Node* nN=new Node(v, weight);
Node* cur=this->list[u-1];
if(cur==nullptr){
list[u-1]=nN;
} else {
while(cur->next!=nullptr) cur=cur->next;
cur->next=nN;
}
}
int Weight(int u, int v){
Node* cur=this->list[u-1];
while(cur!=nullptr && cur->to!=v) cur=cur->next;
return cur->weight;
}
void InitializeSingleSource(int s){
for(int i=0; i<this->nV; ++i){
this->vertex[i].d=INT_MAX;
this->vertex[i].pi=NIL;
}
this->vertex[s-1].d=0;
}
void Relax(int u, int v, int w){
int* Vd=&(this->vertex[v-1].d);
int weightUV=Weight(u, v), Ud=this->vertex[u-1].d;
if(*Vd>Ud+weightUV){
*Vd=Ud+weightUV;
vertex[v-1].pi=u;
}
}
};
차이 제약 시스템과 최단 경로선형 시스템 중 하나인 차이 제약 시스템은 가중치 방향 그래프의 최단 경로를 찾는 문제로 변환할 수 있다.
xj−xi≤bk 의 제약조건을 만족하는 x=(x1,x2,x3,...xn)이라고 할 때,
x+d도 항상 Ax≤b의 해이다.
차이 제약 시스템에서 모든 정점에 도달할 수 있음을 보장하기 위해 v_0를 추가함
==> G가 음의 가중치의 순환을 가지는 경우, 해당 제약 시스템의 해는 존재하지 않는다.
다항식 함수 시간에 동작하는 것을 보장할 수 없는 선형 문제가
차이 제약 시스템인 경우, 벨만 포드 알고리즘을 이용해 O((n+1)(n+m))=O(n^2+m)의 시간에 풀 수 있다.